// JORGE FERNANDO GOMEZ
// 1259371
// 189631
// LEC A1
// MARTIN MÜLLER
// D02
// YANG LIU


#line 10 "hash.c"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "hash.h"
#include "util.h"


/*+*+*+*+*+*+*+*+*+*+*+*
 *   Hash operations   *
 *+*+*+*+*+*+*+*+*+*+*+*/

/* hashInsert() takes a Table hash pointer, checks if string key
 * was already stored in the hash table and if it wasn't, it stores
 * the sat_data fot this key on slot h(k) (computed from hashKey())
 * of Table, or if it was, it updates its node data via hashUpdate()
 * with sat_data. */
void hashInsert ( hash * Table, char * key, void * sat_data ) {
    /* Insert x at the head of list T[ h(x.key) ] */
    int hashedKey = hashKey(Table, key);

    hash_element node = hashRetrieve(Table, key);
    if ( node != NULL ) {
        hashUpdate(node, sat_data);
        return;
    }

    hash_element newNode = calloc(1, sizeof(struct node));
    if ( newNode == NULL )
        killim(__LINE__);

    newNode->data = sat_data;
    newNode->key = key;
    newNode->next = Table->hashTable[hashedKey];

    if ( Table->hashTable[hashedKey] != NULL )
        Table->hashTable[hashedKey]->prev = newNode;

    Table->hashTable[hashedKey] = newNode;
    newNode->prev = NULL;
}

/* hashExists() checks whether string key exists in the hash table Table.
 * It returns false if it didn't, true otherwise. */
bool hashExists ( hash * Table, char * key ) {
    /* Search for an element with key k in list T[ h(k) ] */

    int hashedKey = hashKey(Table, key);
    if ( Table->hashTable[hashedKey] == NULL )
        return false;

    hash_element ptr;
    for (ptr = Table->hashTable[hashedKey]; ptr != NULL; ptr = ptr->next)
        if ( strcmp(ptr->key, key) == 0 )
            return true;
    return false;
}

/* hashRetrieve() takes a hash table Table, and string key, and returns
 * the linked list node for that key if it exists, or NULL otherwise.
 * Note that it returns the actual node pointer (hash_element) and not only
 * the satellite data which was stored for that key. */
hash_element hashRetrieve ( hash * Table, char * key ) {
    /* Search for an element with key k in list T[ h(k) ] */

    int hashedKey = hashKey(Table, key);
    if ( Table->hashTable[hashedKey] == NULL )
        return NULL;

    hash_element ptr;
    for (ptr = Table->hashTable[hashedKey]; ptr != NULL; ptr = ptr->next)
        if ( strcmp(ptr->key, key) == 0 )
            return ptr;
    return (hash_element) NULL;
}

/* hashGetValue(), unlike hashRetrieve, returns the satellite data stored
 * in hash_element member 'data' for a given hash table Table and string key.
 * If key does not exist in the hash table, NULL is returned. */
void* hashGetValue ( hash * Table, char * key ) {
    /* Search for an element with key k in list T[ h(k) ] */

    int hashedKey = hashKey(Table, key);
    if ( Table->hashTable[hashedKey] == NULL )
        killim(__LINE__);

    hash_element ptr;
    for (ptr = Table->hashTable[hashedKey]; ptr != NULL; ptr = ptr->next)
        if ( strcmp((ptr->key), key) == 0 )
            return (ptr->data);

    killim(__LINE__);
    return (void *) NULL;   /* To keep compiler happy. */
}

/* hashDelete() takes a hash table Table and a hash_element aNode and
 * removes aNode from the linked list it lives at, and frees the allocated
 * memory for that node. */
void hashDelete ( hash * Table, hash_element aNode ) {
    /* Delete x from the list T[ h(x.key) ] */

    if ( aNode->prev != NULL )
        (aNode->prev)->next = aNode->next;
    else
        Table->hashTable[hashKey(Table, (aNode->key))] = aNode->next;

    if ( aNode->next != NULL )
        (aNode->next)->prev = aNode->prev;

    free(aNode);
}


/*+*+*+*+*+*+*+*+*+*+*+*
 *    Hash utilities   *
 *+*+*+*+*+*+*+*+*+*+*+*/

/* newHashTable() creates a pointer to a hash struct and
 * allocates size space for the hash_element pointer member
 * inside it.  It calls killim() to terminate if unsuccessful and
 * returns the pointer to the hash otherwise. */
hash* newHashTable ( int size ) {
    /* Allocate space for a hash table. */

    hash * Table = calloc(1, sizeof(hash));
    Table->size = size;
    Table->hashTable = calloc(size, sizeof(hash_element));

    if ( Table->hashTable == NULL )
        killim (__LINE__);

    return Table;
}

/* hashKey() hashes the key provided; that is,
 * it computes the hash value of the key. */
int hashKey ( hash * Table, char * key ) {
    /* Compute index h(k) for key k. */

    int hashed;

    unsigned long rad13_key = 0;
    int rad_base = 13;
    int degree = 0;
    int key_length = strlen(key);

    int i;
    for ( i = key_length-1; i >= 0; i-- ) {
        rad13_key += (key[i] * (Exp(rad_base, degree)));
        degree++;
    }

    int size = Table->size;
    double gratio_conj = 0.6180339887;

    double total = rad13_key * gratio_conj;
    long truncated = total;
    double fraction = total - truncated;

    hashed = (size * fraction);
    return hashed;
}

/* hashUpdate() is called when the key passed
 * to hashInsert() already existed; hashUpdate()
 * then replaces the value stored at this key. */
void hashUpdate( hash_element element, void * sat_data ){
    /* Update a hash value from an existing key. */

    element->data = sat_data;
}
